/*
 * Created on Apr 5, 2005
 * Created by Alon Rohter
 * Copyright (C) Azureus Software, Inc, All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

package com.aelitis.azureus.core.peermanager.unchoker;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Random;

import org.gudy.azureus2.core3.peer.PEPeer;
import org.gudy.azureus2.core3.peer.impl.PEPeerTransport;
import org.gudy.azureus2.core3.util.AENetworkClassifier;
import org.gudy.azureus2.core3.util.RandomUtils;

/**
 * Utility collection for unchokers.
 */
public class UnchokerUtil {

    /**
     * Test whether or not the given peer is allowed to be unchoked.
     * 
     * @param peer
     *            to test
     * @param allow_snubbed
     *            if true, ignore snubbed state
     * @return true if peer is allowed to be unchoked, false if not
     */
    public static boolean isUnchokable(PEPeer peer, boolean allow_snubbed) {
        return (peer.getPeerState() == PEPeer.TRANSFERING && !peer.isSeed() && !peer.isRelativeSeed() && peer.isInterested()
                && !peer.isUploadDisabled() && (!peer.isSnubbed() || allow_snubbed));
    }

    /**
     * Update (if necessary) the given list with the given value while maintaining a largest-value-first (as seen so far) sort order. NOTE: You will
     * need to initialize the values array to Long.MIN_VALUE if you want to store negative values!
     * 
     * @param new_value
     *            to use
     * @param values
     *            existing values array
     * @param new_item
     *            to insert
     * @param items
     *            existing items
     * @param start_pos
     *            index at which to start compare
     */
    public static void updateLargestValueFirstSort(long new_value, long[] values, PEPeer new_item, ArrayList items, int start_pos) {
        items.ensureCapacity(values.length);
        for (int i = start_pos; i < values.length; i++) {
            if (new_value >= values[i]) {
                for (int j = values.length - 2; j >= i; j--) { // shift displaced values to the right
                    values[j + 1] = values[j];
                }

                if (items.size() == values.length) { // throw away last item if list too large
                    items.remove(values.length - 1);
                }

                values[i] = new_value;
                items.add(i, new_item);

                return;
            }
        }
    }

    /**
     * Choose the next peer, optimistically, that should be unchoked.
     * 
     * @param all_peers
     *            list of peer to choose from
     * @param factor_reciprocated
     *            if true, factor in how much (if any) this peer has reciprocated when choosing
     * @param allow_snubbed
     *            allow the picking of snubbed-state peers as last resort
     * @return the next peer to optimistically unchoke, or null if there are no peers available
     */
    public static PEPeer getNextOptimisticPeer(ArrayList<PEPeer> all_peers, boolean factor_reciprocated, boolean allow_snubbed) {

        ArrayList<PEPeer> peers = getNextOptimisticPeers(all_peers, factor_reciprocated, allow_snubbed, 1);

        if (peers != null) {

            return ((PEPeerTransport) peers.get(0));
        }

        return (null);
    }

    public static ArrayList<PEPeer> getNextOptimisticPeers(ArrayList<PEPeer> all_peers, boolean factor_reciprocated, boolean allow_snubbed,
            int num_needed) {
        // find all potential optimistic peers
        ArrayList<PEPeer> optimistics = new ArrayList<PEPeer>();
        for (int i = 0; i < all_peers.size(); i++) {
            PEPeer peer = all_peers.get(i);

            if (isUnchokable(peer, false) && peer.isChokedByMe()) {
                optimistics.add(peer);
            }
        }

        if (optimistics.isEmpty() && allow_snubbed) { // try again, allowing snubbed peers as last resort
            for (int i = 0; i < all_peers.size(); i++) {
                PEPeer peer = all_peers.get(i);

                if (isUnchokable(peer, true) && peer.isChokedByMe()) {
                    optimistics.add(peer);
                }
            }
        }

        if (optimistics.isEmpty())
            return null; // no unchokable peers avail

        // factor in peer reciprocation ratio when picking optimistic peers

        ArrayList<PEPeer> result = new ArrayList<PEPeer>(optimistics.size());

        if (factor_reciprocated) {

            ArrayList<PEPeerTransport> ratioed_peers = new ArrayList<PEPeerTransport>(optimistics.size());
            long[] ratios = new long[optimistics.size()];
            Arrays.fill(ratios, Long.MIN_VALUE);

            // order by upload ratio
            for (int i = 0; i < optimistics.size(); i++) {
                PEPeer peer = optimistics.get(i);

                // score of >0 means we've uploaded more, <0 means we've downloaded more
                long score = peer.getStats().getTotalDataBytesSent() - peer.getStats().getTotalDataBytesReceived();

                UnchokerUtil.updateLargestValueFirstSort(score, ratios, peer, ratioed_peers, 0); // higher value = worse score
            }

            for (int i = 0; i < num_needed && ratioed_peers.size() > 0; i++) {

                double factor = 1F / (0.8 + 0.2 * Math.pow(RandomUtils.nextFloat(), -1)); // map to sorted list using a logistic curve

                int pos = (int) (factor * ratioed_peers.size());

                result.add(ratioed_peers.remove(pos));
            }
        } else {

            for (int i = 0; i < num_needed && optimistics.size() > 0; i++) {

                int rand_pos = new Random().nextInt(optimistics.size());

                result.add(optimistics.remove(rand_pos));
            }
        }

        return (result);

        // TODO:
        // in downloading mode, we would be better off optimistically unchoking just peers we are interested in ourselves,
        // as they could potentially reciprocate. however, new peers have no pieces to share, and are not interesting to
        // us, and would never be unchoked, and thus would never get any data.
        // we could use a deterministic method for new peers to get their very first piece from us
    }

    /**
     * Send choke/unchoke messages to the given peers.
     * 
     * @param peers_to_choke
     * @param peers_to_unchoke
     */
    public static void performChokes(ArrayList<PEPeer> peers_to_choke, ArrayList<PEPeer> peers_to_unchoke) {
        // do chokes
        if (peers_to_choke != null) {
            for (int i = 0; i < peers_to_choke.size(); i++) {
                final PEPeerTransport peer = (PEPeerTransport) peers_to_choke.get(i);

                if (!peer.isChokedByMe()) {
                    peer.sendChoke();
                }
            }
        }

        // do unchokes
        if (peers_to_unchoke != null) {
            for (int i = 0; i < peers_to_unchoke.size(); i++) {
                final PEPeer peer = peers_to_unchoke.get(i);

                if (peer.isChokedByMe()) { // TODO add UnchokerUtil.isUnchokable() test here to be safe?
                    peer.sendUnChoke();
                }
            }
        }
    }

    public static void performChokeUnchoke(PEPeer to_choke, PEPeer to_unchoke) {
        if (to_choke != null && !to_choke.isChokedByMe()) {
            to_choke.sendChoke();
        }

        if (to_unchoke != null && to_unchoke.isChokedByMe()) {
            to_unchoke.sendUnChoke();
        }
    }

    public static void doHighLatencyPeers(ArrayList<PEPeer> peers_to_choke, ArrayList<PEPeer> peers_to_unchoke, boolean allow_snubbed) {

        // when called we don't want to choke high-latency peers

        if (peers_to_choke.size() == 0) {

            return;
        }

        // System.out.println( "doHLP: " + peers_to_choke + ", " + peers_to_unchoke );

        Iterator<PEPeer> choke_it = peers_to_choke.iterator();

        int to_remove = 0;

        while (choke_it.hasNext()) {

            PEPeer peer = choke_it.next();

            if (AENetworkClassifier.categoriseAddress(peer.getIp()) != AENetworkClassifier.AT_PUBLIC) {

                if (isUnchokable(peer, allow_snubbed)) {

                    // System.out.println( "   removed " + peer );

                    choke_it.remove();

                    to_remove++;

                } else {

                    // it isn't unchokable so we need to choke it whatever

                }
            }
        }

        // if we've removed any chokes then we need to balance things by removing an equal number
        // of unchokes

        if (to_remove > 0) {

            ListIterator<PEPeer> unchoke_it = peers_to_unchoke.listIterator(peers_to_unchoke.size());

            // preferrably balance with high latency peers

            while (unchoke_it.hasPrevious()) {

                PEPeer peer = unchoke_it.previous();

                if (AENetworkClassifier.categoriseAddress(peer.getIp()) != AENetworkClassifier.AT_PUBLIC) {

                    // System.out.println( "   balanced with " + peer );

                    unchoke_it.remove();

                    to_remove--;

                    if (to_remove == 0) {

                        return;
                    }
                }
            }

            if (to_remove > 0) {

                unchoke_it = peers_to_unchoke.listIterator(peers_to_unchoke.size());

                while (unchoke_it.hasPrevious()) {

                    PEPeer peer = unchoke_it.previous();

                    unchoke_it.remove();

                    to_remove--;

                    if (to_remove == 0) {

                        return;
                    }
                }
            }
        }
    }
}
